A shared access transport facility (SATF) is a communications medium that can be shared among users simultaneously. A good example of an SATF is the telephone network, since many callers can use the facility to place calls at the same time. Another good example is a local area network (LAN), such as a token ring or an Ethernet LAN. Additionally, networks such as X.25, frame relay and asynchronous transfer mode (ATM) networks are all SATF's. One critical piece of information that must be supplied in any SATF environment to establish communications is the address of the destination. When someone picks up the telephone, they must supply a destination telephone number. In a data network, the user must supply a destination address whose format depends on the medium used. In the LAN environment, for example, a data link control layer address is required, often referred to as a Medium Access Control, or MAC, address or a DLC address.
While a number of protocols exist that provide optimal routing within a SATF in which the topology and node addresses are completely known by the node performing the route calculation, route calculation between a source node in one sub-network and a destination node in another sub-network is often not optimal. To understand why, it is necessary to understand some of the terminology and issues involved in these environments.
A sub-network for purposes of this description is defined as a group of nodes that share routing and topology information. For example, the Internet TCP/IP protocols use Routing Information Protocol (RIP) and the Open Shortest Path First (OSPF) protocol to share this information between nodes. IBM's APPN networking architecture uses Topology Routing Services to share this information. By definition, a sub-network shares routing and topology information among the nodes of the sub-network, but this information is not shared with nodes outside of the sub-network. In other words, a border node in one sub-network may be aware of a link address to a border node in an adjacent sub-network, but will have no further information about the topology of the adjacent sub-network. To set up addressing information from a source node in a first sub-network defined on a SATF to a destination node in another sub-network on the SATF, a route calculation server may be used to calculate a route in the first sub-network between the source node to a border node of the second sub-network. A route-calculating server in the second sub-network can be used to calculate a route between the border node and the destination node. The two routes can then be combined to form the complete route between the source and destination nodes. APPN, for example, operates this way. However, the overall route may not be the shortest or most efficient route between the source and destination nodes. Given this, one may question why implement sub-networks at all. First, as networks get large, the amount of processing required to share the topology and routing information gets large as well. In addition, the amount of storage required to store the information can become prohibitive. Network owners may have security concerns, performance concerns and network management concerns that are resolved by limiting routing and topology information sharing to relatively small sub-networks.
For the moment, IBM's APPN architecture will be used as an example for discussion. An APPN network consists of Network Nodes (NN) and End Nodes (EN) connected in a peer-to-peer relationship. EN's are typically user workstations. NN's provide services, such as route calculation, for EN's. Control Point sessions are established between EN's and NN's for control communications, such as requesting a route calculation or for locating other resources in the network. In the APPN architecture, defining the topology in an SATF so that each node can communicate over the best route with any other node in the SATF represents considerable link definition. This is because each node that is a member of the SATF must have defined in each node all routing information needed to reach any other node over the facility in the most efficient way and the DLC addressing information needed to do so. An example of DLC information is a station address on a token-ring LAN. Because each connection between a pair of nodes on an SATF requires two definitions, one in each node, the number of definitions required is N times (N-1), where N is the number of nodes in the SATF.
A special kind of sub-network, called a virtual routing network (VRN), is used in APPN SATF's to reduce the number of link definitions that are required. An APPN VRN is a representation of a shared access transport facility (SATF) or a portion of a SATF that handles the routing of data among the nodes communicating across the SATF. The VRN allows a reduction in the number of required connection definitions by allowing each node to define a single virtual connection to the VRN. Any node defined as having a connection to a VRN is able to communicate directly with any other node also connected to the same VRN without having to define a connection directly between the two nodes. As a result, the number of definitions required to define meshed connectivity between all nodes on a sub-network defined as a VRN is equal to the number of nodes in the sub-network. Session traffic between two nodes that are defined as being connected to a VRN can be routed directly to one another "through" the VRN without passing through any real node.
To avoid confusion, it is important to understand the distinctions between SATF's, sub-networks and virtual routing networks. A SATF network includes all nodes that communicate over the shared medium of the SATF. A sub-network is a set of nodes in the SATF that share topology and routing information amongst themselves, but not with other nodes in the SATF. A virtual routing network, or VRN, is a fictional entity that is defined to represent a sub-network for the purpose of allowing nodes to define virtual connections to the VRN. A sub-network may or may not be defined as a VRN. If it is defined as a VRN, then the topology and routing information pertaining to the sub-network contains virtual connections from the nodes of the sub-network to the VRN.
To summarize, a VRN representing a SATF or a portion of a SATF allows data to be routed directly between the nodes of the VRN, without necessarily defining real topology connections between the nodes. The VRN does not physically exist, but it allows the nodes to define their logical connections to it in the topology database. Any route calculation between source and destination nodes that are part of the same VRN can determine that the nodes are connected to the same VRN and can thus route data directly to each other using underlying DLC addressing information stored in association with the virtual connections. FIG. 1 illustrates this prior art principle. In FIG. 1, a network consists of an SATF 100, which contains two nodes A and B and a server node S. If it is assumed that FIG. 1 shows an APPN network, then nodes A and B might be end nodes and node S might be a network node that serves the end nodes. It is assumed that all the nodes A, B and S can communicate with each other by means of DLC addressing over a shared access medium. The full shared access medium is not shown in FIG. 1 because it is not particularly relevant to the invention. Rather, FIG. 1 represents a view of the network at a layer higher than the physical layer or the medium access control layer. In FIG. 1, a VRN is defined which represents SATF 100 and is shown by the entity VRN in the center of the network cloud. Nodes A and B are not aware of any connectivity between them. The topology databases of nodes A and S contain an entry for the definition of connection 102 between them. This connection is shown as a bold line in FIG. 1 to illustrate that it is a real defined connection on the shared medium. Connection 102 is the connection over which control point sessions would be established if FIG. 1 represented an APPN network. Similarly, nodes B and S contain a topology database entry for the real defined connection 104 between them. The connections between nodes A, B and S to the VRN are dashed in FIG. 1 to indicate that these are virtual connections to a fictional virtual routing network. When node A initiates or responds to a session initiation request, A tells S that it has a trunk group connection (TG1) to the VRN. Included in the TG1 definition is A's DLC address. Similarly, when node B initiates or responds to a session initiation request, B tells S it has a connection (TG2) to the VRN. Included in TG2 is B's DLC address.
When node A wishes to send information to node B, node A requests node S via the connection 102 to calculate a route to node B. In this example, node S calculates the route EQU A-TG1-VRN-TG2-B
and sends this route to node A. Node A recognizes the VRN in the route as a logical sub-network by a single bit in a node descriptor field in the route which identifies VRN as a virtual routing network. Node A ignores the VRN entry in the calculated route, retrieves B's DLC address from TG2 of the route and sends information directly to this DLC address over the SATF. Note that each node of the VRN need only define one connection to the VRN to reach any other node of the VRN, rather than a definition to every other node.
FIG. 2 illustrates a prior art example similar to FIG. 1, except that in FIG. 2 two sub-networks A and B are defined on the SATF 200; sub-network A is further defined as a virtual routing network VRNA 410 and sub-network B is further defined as a virtual routing network VRNB 412. The example of FIG. 2 illustrates the problem solved by the present invention. VRNA includes nodes A1, A2, and server node SA. VRNB includes nodes B1, B2, and server node SB. All nodes in VRNA define virtual connections, such as TGA1, TGA2 and TGA3, to the virtual routing network VRNA. Likewise, all nodes in VRNB define virtual connections, such as TGB1, TGB2 and TGB3, to the virtual routing network VRNB. In addition, since there are two sub-networks, at least one real connection must be defined between the two sub-networks. This is shown as connection 203 in FIG. 2.
Now assuming that node A2 wishes to communicate with node B2, A2 requests a route calculation from its server SA. SA has no information in its topology database regarding routes in sub-network B. It can find out via a search function that node B2 is in sub-network B by sending a search request to node SB. Node SB is then able to search its topology database and locate node B2. Upon finding node B2, node SB calculates a route from itself to node B2. Node SB knows that node B2 is connected to VRNB and returns a route to node SA of EQU SB-TGB3-VRNB-TGB2-B2.
Node SA calculates a route from node A2 to node SB. Node SA knows that node A2 is connected to VRNA and thus calculates a route of EQU A2-TGA2-VRNA-TGA3-SA-203-SB
Node SA then combines the two route calculations to create the complete end-to-end route of EQU A2-TGA2-VRNA-TGA3-SA-203-SB-TGB3-VRNB-TGB2-B2
When A2 now uses this calculated route to transmit packets to node B2, it recognizes that VRNA in the route is a virtual routing network. Consequently, it skips this part of the route, as well as the logical connection TGA2 leading to it and uses the DLC addressing information contained in TGA3 to route packets directly to node SA over the shared medium. The packets contain the calculated route. SA uses the calculated route in the packets to route them over connection 203 to node SB. Node SB recognizes that VRNB is a virtual routing network representing its sub-network and, as in sub-network A, it skips this part of the calculated route as well as the logical connection TGB3 leading to VRNB. Rather, it obtains addressing information for node B2 from TGB2 and routes the packets directly to node B2 over the shared medium. The result of the above is that packets are inefficiently routed three times on the underlying SATF to get from node A2 to node B2.
The above examples of virtual routing networks allow the routing of packets between nodes of a SATF without the overhead of defining every possible connection within the SATF in the topology databases. And the prior art example of FIG. 2 illustrates how multiple sub-networks can be defined within the SATF to allow network owners flexibility in controlling the topology of their SATF. However, the penalty that is paid for this flexibility is inefficient routing within the SATF. For example, the network of FIG. 2 might be implemented as two token ring LANs A and B tied together with a bridge, as shown in FIG. 3. LAN A represents sub-network VRNA of FIG. 2; LAN B represents sub-network VRNB of FIG. 2. In this example, the calculated route between node A2 and node B2 might be EQU A2-TGA2-VRNA-TGA3-SA-BRIDGE-SB-TGB3-VRNB-TGB2-B2.
A packet from A2 to B2 would first be routed from node A2 to node SA (using DLC addressing information from TGA3). This is once around the ring of LAN A. From node SA, the packet would be sent to the BRIDGE. This is twice around LAN A. The BRIDGE then sends the packet to SB. This is once around LAN B. Finally, node SB sends the packet to B2 using DLC addressing information from TGB2. This is twice around LAN B. Thus, four trips around LAN segments are required in this example, whereas in a SATF with one or no defined sub-networks, but with many connection definitions, only one trip through LAN A and one trip through LAN B is required for the same communication. The invention addresses this problem of inefficient routing when two or more VRNs are defined on a SATF.